/*
 * @lc app=leetcode.cn id=279 lang=golang
 *
 * [279] 完全平方数
 */

// @lc code=start
func numSquares(n int) int {
	memo := make([]int, n+1)
	for i := 1; i <= n; i++ {
		memo[i] = math.MaxInt64
		for j := 1; j*j <= i; j++ {
			memo[i] = min(memo[i], memo[i-j*j]+1)
		}
	}
	return memo[n]
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

// @lc code=end

